/*******************************************************************************
 * Copyright (c) 2003, 2005 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.draw2d.graph;


/**
 * This visitor eliminates cycles in the graph via a modified implementation of the 
 * greedy cycle removal algorithm for directed graphs. The algorithm has been modified to
 * handle the presence of Subgraphs and compound cycles which may result. This algorithm
 * determines a set of edges which can be inverted and result in a graph without compound
 * cycles.
 * 
 * @author Daniel Lee
 * @author Randy Hudson
 * @since 2.1.2
 */
class CompoundBreakCycles extends GraphVisitor {

/*
 * Caches all nodes in the graph. Used in identifying cycles and in cycle removal.
 * Flag field indicates "presence". If true, the node has been removed from the list.
 */ 
private NodeList graphNodes;
private NodeList sL = new NodeList();

private boolean allFlagged(NodeList nodes) {
	for (int i = 0; i < nodes.size(); i++) {
		if (nodes.getNode(i).flag == false)
			return false;
	}
	return true;
}

private int buildNestingTreeIndices(NodeList nodes, int base) {
	for (int i = 0; i < nodes.size(); i++) {
		Node node = (Node)nodes.get(i);
		if (node instanceof Subgraph) {
			Subgraph s = (Subgraph)node;
			s.nestingTreeMin = base;
			base = buildNestingTreeIndices(s.members, base);
		}
		node.nestingIndex = base++;
	}
	return base++;
}

private boolean canBeRemoved(Node n) {
	return !n.flag && getChildCount(n) == 0;
}

private boolean changeInDegree(Node n, int delta) {
	return (n.workingInts[1] += delta) == 0;
}

private boolean changeOutDegree(Node n, int delta) {
	return (n.workingInts[2] += delta) == 0;
}

/*
 * Execution of the modified greedy cycle removal algorithm.
 */
private void cycleRemove(NodeList children) {
	NodeList sR = new NodeList();
	do {
		findSinks(children, sR);	
		findSources(children);
		
		// all sinks and sources added, find node with highest 
		// outDegree - inDegree
		Node max = findNodeWithMaxDegree(children);
		if (max != null) {
			for (int i = 0; i < children.size(); i++) {
				Node child = (Node)children.get(i);
				if (child.flag)
					continue;
				if (child == max)
					restoreSinks(max, sR);
				else
					restoreSources(child);
			}
			remove(max);
		}
	} while (!allFlagged(children));
	while (!sR.isEmpty())
		sL.add(sR.remove(sR.size() - 1));	
}

private void findInitialSinks(NodeList children, NodeList sinks) {
	for (int i = 0; i < children.size(); i++) {
		Node node = children.getNode(i);
		if (node.flag)
			continue;
		if (isSink(node) && canBeRemoved(node)) {
			sinks.add(node);
			node.flag = true;
		}
		if (node instanceof Subgraph)
			findInitialSinks(((Subgraph)node).members, sinks);
	}
}

private void findInitialSources(NodeList children, NodeList sources) {
	for (int i = 0; i < children.size(); i++) {
		Node node = children.getNode(i);
		if (isSource(node) && canBeRemoved(node)) {
			sources.add(node);
			node.flag = true;
		}
		if (node instanceof Subgraph)
			findInitialSources(((Subgraph)node).members, sources);
	}
}

private Node findNodeWithMaxDegree(NodeList nodes) {
	int max = Integer.MIN_VALUE;
	Node maxNode = null;
	
	for (int i = 0; i < nodes.size(); i++) {
		Node node = nodes.getNode(i);
		if (node.flag)
			continue;
		int degree = getNestedOutDegree(node) - getNestedInDegree(node);
		if (degree >= max && node.flag == false) {
			max = degree;
			maxNode = node;
		}
	}
	return maxNode;
}

/*
 * Finds all sinks in graphNodes and adds them to the passed NodeList
 */
private void findSinks(NodeList children, NodeList rightList) {
//	NodeList rightList = new NodeList();
	NodeList sinks = new NodeList();
	findInitialSinks(children, sinks);
	while (!sinks.isEmpty()) {
		Node sink = sinks.getNode(sinks.size() - 1);
		rightList.add(sink);
		sinks.remove(sink);
		removeSink(sink, sinks);
		
		// Check to see if the removal has made the parent node a sink
		if (sink.getParent() != null) {
			Node parent = sink.getParent();
			setChildCount(parent, getChildCount(parent) - 1);
			if (isSink(parent) && canBeRemoved(parent)) {
				sinks.add(parent);
				parent.flag = true;
			}
		}
	}
}

/*
 * Finds all sources in graphNodes and adds them to the sL NodeList.
 */
private void findSources(NodeList children) {
	NodeList sources = new NodeList();
	findInitialSources(children, sources);
	while (!sources.isEmpty()) {
		Node source = sources.getNode(sources.size() - 1);
		sL.add(source);
		sources.remove(source);
		removeSource(source, sources);
	
		// Check to see if the removal has made the parent node a source
		if (source.getParent() != null) {
			Node parent = source.getParent();
			setChildCount(parent, getChildCount(parent) - 1);
			if (isSource(parent) && canBeRemoved(parent)) {
				sources.add(parent);
				parent.flag = true;
			}
		}
	}
}

private int getChildCount(Node n) {
	return n.workingInts[3];
}	

private int getInDegree(Node n) {
	return n.workingInts[1];
}

private int getNestedInDegree(Node n) {
	int result = getInDegree(n);
	if (n instanceof Subgraph) {
		Subgraph s = (Subgraph)n;
		for (int i = 0; i < s.members.size(); i++)
			if (!s.members.getNode(i).flag)
				result += getInDegree(s.members.getNode(i));
	}
	return result;
}

private int getNestedOutDegree(Node n) {
	int result = getOutDegree(n);
	if (n instanceof Subgraph) {
		Subgraph s = (Subgraph)n;
		for (int i = 0; i < s.members.size(); i++)
			if (!s.members.getNode(i).flag)
				result += getOutDegree(s.members.getNode(i));
	}
	return result;
}

private int getOrderIndex(Node n) {
	return n.workingInts[0];
}

private int getOutDegree(Node n) {
	return n.workingInts[2];
}

private void initializeDegrees(DirectedGraph g) {
	g.nodes.resetFlags();
	g.edges.resetFlags(false);
	for (int i = 0; i < g.nodes.size(); i++) {
		Node n = g.nodes.getNode(i);
		setInDegree(n, n.incoming.size());
		setOutDegree(n, n.outgoing.size());
		if (n instanceof Subgraph)
			setChildCount(n, ((Subgraph)n).members.size());
		else
			setChildCount(n, 0);
	}
}

private void invertEdges(DirectedGraph g) {
	// Assign order indices
	int orderIndex = 0;
	for (int i = 0; i < sL.size(); i++) {
		setOrderIndex(sL.getNode(i), orderIndex++);
	}
	// Invert edges that are causing a cycle
	for (int i = 0; i < g.edges.size(); i++) {
		Edge e = g.edges.getEdge(i);
		if (getOrderIndex(e.source) > getOrderIndex(e.target)
		  && !e.source.isNested(e.target)
		  && !e.target.isNested(e.source)) {
			e.invert();
			e.isFeedback = true;
		}
	}
}

/**
 * Removes all edges connecting the given subgraph to other nodes outside of it.
 * @param s
 * @param n
 */
private void isolateSubgraph(Subgraph subgraph, Node member) {
	Edge edge = null;
	for (int i = 0; i < member.incoming.size(); i++) {
		edge = member.incoming.getEdge(i);
		if (!subgraph.isNested(edge.source) && !edge.flag)
			removeEdge(edge);
	}
	for (int i = 0; i < member.outgoing.size(); i++) {
		edge = member.outgoing.getEdge(i);
		if (!subgraph.isNested(edge.target) && !edge.flag)
			removeEdge(edge);
	}
	if (member instanceof Subgraph) {
		NodeList members = ((Subgraph)member).members;
		for (int i = 0; i < members.size(); i++)
			isolateSubgraph(subgraph, members.getNode(i));
	}
}

private boolean isSink(Node n) {
	return getOutDegree(n) == 0
		&& (n.getParent() == null
			|| isSink(n.getParent()));
}

private boolean isSource(Node n) {
	return  getInDegree(n) == 0
		&& (n.getParent() == null
			|| isSource(n.getParent()));
}

private void remove(Node n) {
	n.flag = true;
	if (n.getParent() != null)
		setChildCount(n.getParent(), getChildCount(n.getParent()) - 1);
	removeSink(n, null);
	removeSource(n, null);
	sL.add(n);
	if (n instanceof Subgraph) {
		Subgraph s = (Subgraph)n;
		isolateSubgraph(s, s);
		cycleRemove(s.members);
	}
}

private boolean removeEdge(Edge e) {
	if (e.flag)
		return false;
	e.flag = true;
	changeOutDegree(e.source, -1);
	changeInDegree(e.target, -1);
	return true;
}

/**
 * Removes all edges between a parent and any of its children or descendants.
 */
private void removeParentChildEdges(DirectedGraph g) {
	for (int i = 0; i < g.edges.size(); i++) {
		Edge e = g.edges.getEdge(i);
		if (e.source.isNested(e.target) || e.target.isNested(e.source))
			removeEdge(e);
	}
}

private void removeSink(Node sink, NodeList allSinks) {
	for (int i = 0; i < sink.incoming.size(); i++) {
		Edge e = sink.incoming.getEdge(i);
		if (!e.flag) {
			removeEdge(e);
			Node source = e.source;
			if (allSinks != null && isSink(source) && canBeRemoved(source)) {
				allSinks.add(source);
				source.flag = true;
			}
		}
	}
}

private void removeSource(Node n, NodeList allSources) {
	for (int i = 0; i < n.outgoing.size(); i++) {
		Edge e = n.outgoing.getEdge(i);
		if (!e.flag) {
			e.flag = true;
			changeInDegree(e.target, -1);
			changeOutDegree(e.source, -1);
			
			Node target = e.target;
			if (allSources != null && isSource(target) && canBeRemoved(target)) {
				allSources.add(target);
				target.flag = true;
			}
		}
	}
}

/**
 * Restores an edge if it has been removed, and both of its nodes are not removed.
 * @param e the edge
 * @return <code>true</code> if the edge was restored
 */
private boolean restoreEdge(Edge e) {
	if (!e.flag || e.source.flag || e.target.flag)
		return false;
	e.flag = false;
	changeOutDegree(e.source, 1);
	changeInDegree(e.target, 1);
	return true;
}

/**
 * Brings back all nodes nested in the given node.
 * @param node the node to restore
 * @param sr current sinks
 */
private void restoreSinks(Node node, NodeList sR) {
	if (node.flag && sR.contains(node)) {
		node.flag = false;
		if (node.getParent() != null)
			setChildCount(node.getParent(), getChildCount(node.getParent()) + 1);
		sR.remove(node);
		for (int i = 0; i < node.incoming.size(); i++) {
			Edge e = node.incoming.getEdge(i);
			restoreEdge(e);
		}
		for (int i = 0; i < node.outgoing.size(); i++) {
			Edge e = node.outgoing.getEdge(i);
			restoreEdge(e);
		}
	}
	if (node instanceof Subgraph) {
		Subgraph s = (Subgraph)node;
		for (int i = 0; i < s.members.size(); i++) {
			Node member = s.members.getNode(i);
			restoreSinks(member, sR);
		}
	}
}

/**
 * Brings back all nodes nested in the given node.
 * @param node the node to restore
 * @param sr current sinks
 */
private void restoreSources(Node node) {
	if (node.flag && sL.contains(node)) {
		node.flag = false;
		if (node.getParent() != null)
			setChildCount(node.getParent(), getChildCount(node.getParent()) + 1);
		sL.remove(node);
		for (int i = 0; i < node.incoming.size(); i++) {
			Edge e = node.incoming.getEdge(i);
			restoreEdge(e);
		}
		for (int i = 0; i < node.outgoing.size(); i++) {
			Edge e = node.outgoing.getEdge(i);
			restoreEdge(e);
		}
	}
	if (node instanceof Subgraph) {
		Subgraph s = (Subgraph)node;
		for (int i = 0; i < s.members.size(); i++) {
			Node member = s.members.getNode(i);
			restoreSources(member);
		}
	}
}

public void revisit(DirectedGraph g) {
	for (int i = 0; i < g.edges.size(); i++) {
		Edge e = g.edges.getEdge(i);
		if (e.isFeedback())
			e.invert();
	}
}

private void setChildCount(Node n, int count) {
	n.workingInts[3] = count;
}

private void setInDegree(Node n, int deg) {
	n.workingInts[1] = deg;
}

private void setOrderIndex(Node n, int index) {
	n.workingInts[0] = index;
}

private void setOutDegree(Node n, int deg) {
	n.workingInts[2] = deg;
}

/**
 * @see GraphVisitor#visit(org.eclipse.draw2d.graph.DirectedGraph)
 */
public void visit(DirectedGraph g) {
	initializeDegrees(g);
	graphNodes = g.nodes;
	
	NodeList roots = new NodeList();
	for (int i = 0; i < graphNodes.size(); i++) {
		if (graphNodes.getNode(i).getParent() == null)
			roots.add(graphNodes.getNode(i));
	}
	buildNestingTreeIndices(roots, 0);
	removeParentChildEdges(g);
	cycleRemove(roots);
	invertEdges(g);
}

}
